// tag : 1 表示指向子节点 ，2 表示指向前驱后继
class Node {
    data
    leftTag
    left
    rightTag
    right

    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
        this.leftTag = null;
        this.leftTag = null;
    }
}

class Tree {
    node
    info

    constructor(info) {
        this.info = info || {};
        this.node = null;
    }

    insert(node) {
        if (!(node instanceof Node)) {
            node = new Node(node);
        }

        if (!this.node) {
            this.node = node;
        } else {
            this._insert(this.node, node);
        }
    }

    _insert(root, node) {
        if (node.data < root.data) {
            if (root.left) {
                this._insert(root.left, node);
            } else {
                root.leftTag = 1;
                root.left = node;
                node.leftTag = 2;
                node.leftTag = root;
            }
        } else {
            if (root.right) {
                this._insert(root.right, node);
            } else {
                root.rightTag = 1;
                root.right = node;
            }
        }
    }

    // 线索化
    genIndex() {
        this._genIndex(this.node);
    }
    _genIndex(node) {
        if (node) {
            this._genIndex(node.left);
            if (!node.left) {
                node.left = this.info.pre;
                node.leftTag = 2;
            }
        }
    }
    find() {

    }
}

let tree = new Tree();
let nodeCount = 10;
while (nodeCount-- > 0) {
    tree.insert(parseInt(Math.random() * 100));
}
console.log(tree)